#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        } else {
            // Move the accessed node to the front of the list
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            return cacheMap[key]->second;
        }
    }

    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            // Update the value and move the node to the front of the list
            cacheMap[key]->second = value;
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        } else {
            if (cacheList.size() == capacity) {
                // Remove the least recently used item
                int lruKey = cacheList.back().first;
                cacheList.pop_back();
                cacheMap.erase(lruKey);
            }
            // Insert the new key-value pair
            cacheList.emplace_front(key, value);
            cacheMap[key] = cacheList.begin();
        }
    }

private:
    int capacity;
    std::list<std::pair<int, int>> cacheList;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cacheMap;
};

int main() {
    LRUCache cache(2); // Capacity of 2
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << std::endl; // Returns 1
    cache.put(3, 3); // Evicts key 2
    std::cout << cache.get(2) << std::endl; // Returns -1 (not found)
    cache.put(4, 4); // Evicts key 1
    std::cout << cache.get(1) << std::endl; // Returns -1 (not found)
    std::cout << cache.get(3) << std::endl; // Returns 3
    std::cout << cache.get(4) << std::endl; // Returns 4
    return 0;
}
